#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    public:
    
    bool ans1(TreeNode* root){
        if(root == nullptr){
            return true;
        }

        vector<int> frontval;
        myfrontTraverse(root, frontval);
        change(root);
        vector<int> afterval;
        myfrontTraverse(root, afterval);
        for(int i = 0; i != frontval.size(); i++){
            if(frontval[i] != afterval[i]){
                return false;
            }
        }
        return true;
        
    }

    TreeNode* change(TreeNode* root){
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        change(root->left);
        change(root->right);
        return root;
    }

    bool ans2(TreeNode* root){
        if(!root){
            return true;
        }

        return isSame(root->left, root->right);
    }

    bool isSame(TreeNode* lp, TreeNode* rp){
        if(!lp && !rp){
            return true;
        }
        if(!lp || !rp){
            return false;
        }
        if(lp->val == rp->val && isSame(lp->left, rp->right) && isSame(lp->right, rp->left)){
            return true;
        }else{
            return false;
        }
    }
    

    void frontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->right, val);
        frontTraverse(root->left, val);
    }

    void myfrontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            val.push_back(-INT16_MAX);
            return;
        }
        val.push_back(root->val);
        myfrontTraverse(root->left, val);
        myfrontTraverse(root->right, val);
    }


    TreeNode* createTree(vector<int> nums, int index, int len){
        if(nums[index] == '#'){
            return NULL;
        }
        TreeNode* root = new TreeNode(nums[index]);

        if(index * 2 + 1 < len){
            root->left = createTree(nums, index * 2 + 1, len);
        }else{
            root->left = NULL;
        }
        if(index * 2 + 2 < len){
            root->right = createTree(nums, index * 2 + 2, len);
        }else{
            root->right = NULL;
        }
        return root;
    }

    void show(vector<int>& val){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
        val.clear();
    }

};

void test1(){
    Solution s;

    vector<int> num = {1,2,2,3,4,4,3};
    TreeNode* root = s.createTree(num, 0, num.size());
    vector<int> val;
    // s.frontTraverse(root, val);
    // s.show(val); val.clear();
    // bool ret = s.ans1(root);
    bool ret = s.ans2(root);
    cout << ret << endl;
    
}

void test2(){
    Solution s;

    vector<int> num = {1,2,2,'#',3,'#',3};
    TreeNode* root = s.createTree(num, 0, num.size());
    vector<int> val;
    // s.frontTraverse(root, val);
    // s.show(val); val.clear();
    bool ret = s.ans1(root);
    cout << ret << endl;
}


int main(void){
    test1();
    test2();

    return 0;
}